The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
Stylized Representation of Roads and Similar Features on Digital Maps
For information clarity, roads, bicycle paths, transit lines, and similar features are represented on digital maps in a stylized, rather than a realistic, form. For example, the style in which a road segment is represented on a digital map can include a set of visual parameters such as the number of strokes (e.g., one for the outline and one for the fill color), per-stroke attributes such as stroke width, stroke color, etc. The width of the stroke generally does not scale in proportion to the real-life width of the road, because doing so would make most roads invisible or barely visible at certain zoom levels.
In order to conserve bandwidth, a network server typically provides definitions of styles for rendering roads and other map features at several discrete zoom levels. In some cases, the network server does not provide style definitions for every discrete zoom level in the valid range. Thus, for example, the network server may provide style definitions for roads only at discrete zoom levels N and N+2, even if a client device at some point may display a digital map at zoom level N+1. Moreover, on some devices, such as smartphones and tablet computers capable of receiving gesture input, zoom levels form a continuum rather than a discrete scale. It is therefore possible for a client device to display a digital map at zoom level 7.5 or 8.45, for example. However, it is impractical for the server to attempt to provide style data to client devices for hundreds or thousands of fractional zoom levels.
When style information is unavailable for a certain zoom level, it is difficult for the client device to estimate the visual parameters both accurately and efficiently, and when estimates of visual parameters are not accurate or generated slowly, there are noticeable abrupt transitions (or “popping”) between representations of roads as the user scales across certain zoom levels. In addition to sudden transitions in width (e.g., from three pixels to six), the user may notice abrupt displacement of graphics elements forming patterns on representations of roads, such as repeating arrows indicating the direction of travel along one-way streets. For example, the user may notice that arrows “jump” around to make room for additional arrows or to close gaps left by arrows that were removed.
Modern Hardware Graphics Renderers
To render stylized roads and other features as discussed above, a typical client device utilizes a hardware graphics renderer in a Graphics Processing Unit (GPU), that implements two pipeline shading stages: vertex shaders that operate on vertices visible in a frame and fragment shaders that operate on “fragments,” or sets of pixels that make up a frame. For example, the client device can create a collection of triangles (made up of points defined in two or three dimensions) and pass the collection of triangles to the GPU. For each triangle T in the collection, the GPU then can run a vertex shader on each vertex of triangle T, and a fragment shader on each pixel enclosed by triangle T.
Modern hardware 3D graphics renderers, such as an OpenGL ES renderer, perform optimally when rendering state changes are minimal with respect to the amount of data being drawn. The basic I/O model of these hardware renderers can be described as follows: the renderers receive vertices and texture (pixel) data and produce fragments. Generally speaking, to render a frame of information on a hardware graphics renderer, the following steps are taken: (1) the region in memory for storing bitmaps, known as a “framebuffer,” is cleared and (2) for each logical object in the rendered frame: (2a) vertex and texture data are prepared for rendering, (2b) the state of the graphics pipeline is set, and (2c) a draw function to draw the data is executed.
Step (2c) above describes a common programming loop. Accordingly, the fewer iterations there are of step (2c), the better the software application will perform. This principle of maximizing rendering performance can be referred to as “batching.” To comply with the principle, software applications must batch together as many like elements of graphics state and draw these like elements atomically.
Another important principle for maximizing performance is to minimize shading logic. Vertex shaders are executed once per vertex for objects visible in a frame being rendered, whereas fragment shaders are executed once per output pixel (fragment) of the frame. A typical modern display may contain millions of pixels in an output frame and tens of thousands of vertices. To perform better, software applications must reduce the complexity of these shaders that must be run so frequently.